package com.zxy.javaarithmetic.chapter_2_LinkList;

/*
 *  @项目名：  study
 *  @包名：    com.zxy.javaarithmetic.chapter_2_LinkList
 *  @文件名:   P_3_RemoveMidNode
 *  @创建者:   zhangxy
 *  @创建时间:  2018/12/7 15:24
 *  @描述：    实现两个函数：删除链表中间节点和删除a/b处的节点
 */
public class P_3_RemoveMidNode {

	public static void main(String[] args) {
		Node head = LinkListUtils.getNode(6);

		LinkListUtils.printNode(head);
		LinkListUtils.printNode(removeMidNode(head));

		LinkListUtils.printNode(removeNodeByRatio(head, 3, 5));
	}

	/**
	 * 删除链表中间节点，例如: 长度   删除的节点
	 *                     1     不删除节点
	 *                     2        1
	 *                     3        2
	 *                     4        2
	 *                     5        3
	 * 我们可以计算出链表长度，然后找到中间节点的前一个节点，然后删除中间节点。但是
	 * 这样做并不是最好的方法
	 * @param head
	 */
	private static Node removeMidNode(Node head) {
		if (head == null || head.next == null) {
			return head;
		}
		if (head.next.next == null) {
			return head.next;
		}
		Node pre = head;
		Node cur = head.next.next;
		while (cur.next != null && cur.next.next != null) {
			pre = pre.next;
			cur = cur.next.next;
		}
		pre.next = pre.next.next;
		return head;
	}

	private static Node removeNodeByRatio(Node head, int a, int b) {
		if (head == null || a == 0 || b == 0 || a > b) {
			return head;
		}

		//计算链表长度
		int n = 0;
		Node cur = head;
		while (cur != null) {
			n++;
			cur = cur.next;
		}

		//要删除的节点位置
		int index = (int) Math.ceil(a * n / b);
		if (index == 1) {
			head = head.next;
		} else if (index > 1) {
			Node pre = head;
			while (--index != 1) {
				pre = pre.next;
			}
			pre.next = pre.next.next;
		}

		return head;
	}


}
